class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 厄拉多塞筛法
        if n<3:
            return 0
        # 首先生成一个全部为1的列表
        output = [1] * n
        output[0],output[1] = 0,0
        for i in range(2,int(n**0.5)+1):  # 根据下边从i*i开始的来定义范围
            if output[i] == 1: #如果i为质数
                output[i*i:n:i] = [0] * len(output[i*i:n:i])# 将i的倍数置为0 (比i小的倍数都被清了，从i的i倍开始清)
        return sum(output)